home *** CD-ROM | disk | FTP | other *** search
/ The Programmer Disk / The Programmer Disk (Microforum).iso / xpro / c / pro14 / makeskip.c < prev    next >
Encoding:
C/C++ Source or Header  |  1986-04-02  |  1.3 KB  |  41 lines
  1. #include "bm.h"
  2. MakeSkip(Pattern,Skip1,Skip2,PatLen)
  3. char Pattern[];
  4. int Skip1[], Skip2[];
  5. int PatLen;
  6. /* generate the skip tables for Boyer-Moore string search algorithm.
  7. * Skip1 is the skip depending on the character which failed to match
  8. * the pattern, and Skip2 is the skip depending on how far we got into
  9. * the pattern. Pattern is the search pattern and PatLen is strlen(Pattern) */
  10. {
  11.     int *BackTrack; /* backtracking table for t when building skip2 */
  12.     int c; /* general purpose constant */
  13.     int j,k,t,tp; /* indices into Skip's and BackTrack */
  14.  
  15.     BackTrack = (int *) calloc(PatLen,sizeof (int));
  16.     for (c=0; c<=MAXCHAR; ++c)
  17.         Skip1[c] = PatLen;
  18.     for (k=0;k<PatLen;k++) {
  19.         Skip1[Pattern[k]] = PatLen - k - 1;
  20.         Skip2[k] = 2 * PatLen - k - 1;
  21.     } /* for */
  22.     for (j=PatLen - 1,t=PatLen;j >= 0; --j,--t) {
  23.         BackTrack[j] = t;
  24.         while (t<PatLen && Pattern[j] != Pattern[t]) {
  25.             Skip2[t] = min(Skip2[t], PatLen - j - 1);
  26.             t = BackTrack[t];
  27.         } /* while */
  28.     } /* for */
  29.     for (k=0;k<=t;++k)
  30.         Skip2[k] = min(Skip2[k],PatLen+t-k);
  31.     tp=BackTrack[t];
  32.     while(tp<PatLen) {
  33.         while(t<PatLen) {
  34.             Skip2[t] = min(Skip2[t],tp-t+PatLen);
  35.             ++t;
  36.         } /* while */
  37.         tp = BackTrack[tp];
  38.     } /* while */
  39.     cfree(BackTrack);
  40. } /* MakeSkip */
  41.